M2.992 · Anàlisi de xarxes complexes
20251 - Màster universitari en Ciència de dades (Data science)
Estudis d'Informàtica, Multimèdia i Telecomunicacions
El dia en què es durà a terme aquesta avaluació es publicarà al fòrum de l’assignatura i/o a l’apartat d’Anuncis amb prou antelació. L’avaluació es farà sobre una mostra de l’alumnat que comprendrà entre el 10% i el 35% del total. Aquesta mostra podrà ser aleatòria o dirigida. Un mateix estudiant pot ser avaluat en una, diverses o totes les PAC. Per això, es posaran a disposició dels estudiants diversos slots disponibles i s’avisarà amb 24 hores d’antelació a aquells que hauran de realitzar aquesta avaluació.
L’avaluació de les entregues en període extraordinari es durà a terme durant les últimes setmanes del curs.
- https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4161295/
- https://www.quanthub.com/designing-charts-axes-and-value-labels/
Disenyar i representar de forma correcta informació gràfica és una competència transversal que s'ha d'adquirir.
Alguns punts fonamentals:
- LLegendes clares i informatives incloent-hi les seves unitats.
- El format de les línies, punts i representacions gràfiques ha de ser tan informatiu i clar com sigui possible.
- Els textos superposats sobre altres textos o sobre informació gràfica es puntuarà, en general, de manera molt negativa.
PEC 2: Detecció de comunitats i fluxos d'informació¶
En aquesta pràctica revisarem i aplicarem els coneixements apresos en els mòduls 2 i 3.
Les competències que es treballaran en aquesta activitat són les següents:
- Aprofundir en la comprensió de les propietats de les xarxes complexes que s’observen en dades empíriques.
- Conèixer i implementar alguns dels principals mètodes de detecció de comunitats en grafs.
- Conèixer i implementar les principals tècniques i models de fluxos d’informació en el context de la propagació epidèmica.
- Entendre l’estreta relació que emergeix entre l’estructura i la dinàmica d’una xarxa complexa en el context de la detecció de comunitats i les dinàmiques de propagació.
Consideracions generals:
- Aquesta prova d’avaluació s’ha de resoldre utilitzant la biblioteca
NetworkXi les altres biblioteques importades en l’enunciat. L’ús de qualsevol altra biblioteca s’ha de justificar dins de la mateixa activitat. - Aquesta PEC s’ha de realitzar de manera estrictament individual. Qualsevol indici de còpia serà penalitzat amb un suspens (D) per a totes les parts implicades i pot comportar l’avaluació negativa de l’assignatura de manera íntegra.
- És necessari que l’estudiant indiqui totes les fonts que ha utilitzat per a la realització de la PEC. En cas contrari, es considerarà que l’estudiant ha comès plagi, i serà penalitzat amb un suspens (D) i la possible avaluació negativa de l’assignatura de manera íntegra.
Format del lliurament:
- Alguns exercicis poden requerir diversos minuts d’execució, per la qual cosa el lliurament s’ha de fer en format notebook i en format HTML, on s’hi vegi el codi, els resultats i els comentaris de cada exercici. Es pot exportar el notebook a HTML des del menú File → Download as → HTML.
- Hi ha un tipus de cel·la especial per incloure text. Aquest tipus de cel·la us serà molt útil per respondre les diferents preguntes teòriques plantejades al llarg de l’activitat. Per canviar el tipus de cel·la, aneu al menú: Cell$\to$ Cell Type $\to$ Markdown.
Càrrega de llibreries¶
A la cel·la següent s’han de carregar totes les biblioteques necessàries per a l’execució de l’activitat. En general, es poden utilitzar altres biblioteques, sempre que s’hi justifiqui el seu ús.
!pip install scipy
Requirement already satisfied: scipy in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (1.16.3) Requirement already satisfied: numpy<2.6,>=1.25.2 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from scipy) (1.26.4)
# Llibreries bàsiques
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import itertools
import random
from scipy.integrate import odeint
# Llibreries addicionals (justificar el seu ús)
%matplotlib inline
Les versions de les biblioteques que es recomanen per a aquesta activitat són les següents. No és necessari utilitzar exactament aquestes versions, però són amb les quals s’ha provat la solució.
- NetworkX ver. 3.2.1
- Pandas ver. 2.2.3
- Numpy ver. 1.26.4
# Comprobar les versions
print("NetworkX ver. {}".format(nx.__version__))
print("Pandas ver. {}".format(pd.__version__))
print("Numpy ver. {}".format(np.__version__))
NetworkX ver. 3.2.1 Pandas ver. 2.2.3 Numpy ver. 1.26.4
Analitzant les xarxes d’interacció entre dofins mulars a Florida¶
En l’article titulat “The importance of delineating networks by activity type in bottlenose dolphins (Tursiops truncatus) in Cedar Key, Florida” [1], publicat a la revista Royal Society Open Science, els autors proposen una anàlisi de xarxes socials en una població de dofins mulars salvatges observats a la costa de Florida.
L’estudi parteix d’una idea fonamental en l’anàlisi de xarxes socials animals: les interaccions entre individus poden variar significativament segons el context o l’activitat que estiguin realitzant. En aquest cas, els investigadors distingeixen entre diferents tipus de comportament i construeixen xarxes específiques per a cada activitat observada.
Aquest enfocament permet explorar com la morfologia de la xarxa —és a dir, la seva estructura i propietats— pot canviar en funció del context, i com aquestes diferències poden tenir implicacions importants en processos com la propagació d’informació o d’epidèmies.
Aquest conjunt de dades representa, per tant, una oportunitat excel·lent per aplicar els coneixements adquirits sobre anàlisi de xarxes complexes a un cas empíric real, i per reflexionar sobre la relació entre estructura i dinàmica en sistemes socials no humans.
[1] Gazda, S., Iyer, S., Killingback, T., Connor, R., & Brault, S. (2015). The importance of delineating networks by activity type in bottlenose dolphins (Tursiops truncatus) in Cedar Key, Florida. Royal Society Open Science, 2(3), 140263. https://doi.org/10.1098/rsos.140263
Important: A la carpeta data trobaràs els fitxers dolphin-florida-social.csv i dolphin-florida-forage.csv. Aquests fitxers contenen les arestes amb pesos perquè, un cop importats, puguis crear els grafs per resoldre els exercicis corresponents.
a) A partir de la creació i un análisi descriptiu bàsic dels grafs obtinguts, corrobora el que hi ha descrit a l'article en referència a les xarxes de socialització i d'alimentació de dofins. Comenta amb les teves paraules les seves diferències morfològiques.(0,75 punts)
b) Realitza una visualització senzilla en la que es vegi l'estructura general de cada graf, complementant el que has obtingut a l'apartat anterior. (0,25 punts)
A partir de l'observació de les mètriques obtingudes, es corroboren els resultats de l'article pel que fa a la xarxa de socialització i a la xarxa d'alimentació.
La xarxa de socialització presenta un elevat grau mitjà, fet que indica que cada node de la xarxa té moltes connexions amb altres nodes, és a dir que cada dofí es relaciona amb molts altres dofins. En la xarxa d'alimentació, passa el contrari, el grau mitjà es més baix, per tant, en la xarxa de alimentació els dofins no es relaciaonaran tant amb altres dofins com en les interaccions de socialització.
La xarxa de relacions socials presenta una average strength més elevada que la de la xarxa d'alimentació. Per tant, en la xarxa de socialització, les relacions entre nodes son més fortes que en la xarxa d'alimentació; és a dir, en termes de morfologia, en la xarxa de socialització, als nodes hi incideix més pes de mitjana (pes de les arestes) que a la xarxa d'alimentació. A més la xarxa de socialització, presenta un major pes promig que la xarxa d'alimentació. Per tant, les relacions entre nodes (dofins) són més fortes/intenses en el moment de socialitzar.
En la xarxa d'alimentació és pot observar que hi ha més components connexes que en la xarxa de socialització. Això indica que per socialitzar, els dofins interactuen més entre ells. és a dir que formen menys grups aillats. A més la menor presència de comunitats en la xarxa de socialització, indica que els dofins tendeixen a no formar "grupets" (grups de nodes molt connectats entre ells). Finalment també sobserva que, en la xarxa de socialització la mida de les comunitats és major que en la xarxa d'alimentació, per tant, els dofins formen "grups" més grans a l'hora de socialitzar.
# Bibliografia: [Ref.2] --> Ús 3
# ----- Lectura del csv i preparació de les arestes amb pesos -----
edges_weights = [] # Per guardar tuples (node1, node2, pes)
with open("data/dolphin-florida-social.csv") as f:
for line in f:
splitted_line = line.split(" ")
triple = (splitted_line[0].strip(), splitted_line[1].strip(), int(splitted_line[2].strip()))
edges_weights.append(triple)
f.close()
# ----- Construcció del graf de socialització a partir de les arestes i els pesos anteriorment obtinguts del fitxer -----
socialization_graph = nx.Graph()
socialization_graph.add_weighted_edges_from(edges_weights) # Bibliografia: [Ref.1]
!pip install cdlib
Requirement already satisfied: cdlib in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (0.4.0) Requirement already satisfied: numpy in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (1.26.4) Requirement already satisfied: scikit-learn in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (1.7.2) Requirement already satisfied: tqdm in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (4.67.1) Requirement already satisfied: networkx>=3.0 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (3.2.1) Requirement already satisfied: demon in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (2.0.6) Requirement already satisfied: python-louvain>=0.16 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (0.16) Requirement already satisfied: scipy>=1.10 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (1.16.3) Requirement already satisfied: pulp in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (3.3.0) Requirement already satisfied: seaborn in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (0.13.2) Requirement already satisfied: pandas in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (2.2.3) Requirement already satisfied: eva-lcd in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (0.1.1) Requirement already satisfied: bimlpa in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (0.1.2) Requirement already satisfied: python-igraph>=0.10 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (1.0.0) Requirement already satisfied: angelcommunity in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (2.0.0) Requirement already satisfied: pooch in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (1.8.2) Requirement already satisfied: dynetx in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (0.3.2) Requirement already satisfied: thresholdclustering in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (1.1) Requirement already satisfied: python-Levenshtein in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (0.27.3) Requirement already satisfied: plotly in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from cdlib) (6.4.0) Requirement already satisfied: igraph==1.0.0 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from python-igraph>=0.10->cdlib) (1.0.0) Requirement already satisfied: texttable>=1.6.2 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from igraph==1.0.0->python-igraph>=0.10->cdlib) (1.7.0) Requirement already satisfied: future in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from angelcommunity->cdlib) (1.0.0) Requirement already satisfied: matplotlib in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from bimlpa->cdlib) (3.10.7) Requirement already satisfied: decorator in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from dynetx->cdlib) (5.2.1) Requirement already satisfied: contourpy>=1.0.1 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from matplotlib->bimlpa->cdlib) (1.3.3) Requirement already satisfied: cycler>=0.10 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from matplotlib->bimlpa->cdlib) (0.12.1) Requirement already satisfied: fonttools>=4.22.0 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from matplotlib->bimlpa->cdlib) (4.60.1) Requirement already satisfied: kiwisolver>=1.3.1 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from matplotlib->bimlpa->cdlib) (1.4.9) Requirement already satisfied: packaging>=20.0 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from matplotlib->bimlpa->cdlib) (25.0) Requirement already satisfied: pillow>=8 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from matplotlib->bimlpa->cdlib) (12.0.0) Requirement already satisfied: pyparsing>=3 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from matplotlib->bimlpa->cdlib) (3.2.5) Requirement already satisfied: python-dateutil>=2.7 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from matplotlib->bimlpa->cdlib) (2.9.0.post0) Requirement already satisfied: six>=1.5 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from python-dateutil>=2.7->matplotlib->bimlpa->cdlib) (1.17.0) Requirement already satisfied: pytz>=2020.1 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from pandas->cdlib) (2025.2) Requirement already satisfied: tzdata>=2022.7 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from pandas->cdlib) (2025.2) Requirement already satisfied: narwhals>=1.15.1 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from plotly->cdlib) (2.10.2) Requirement already satisfied: platformdirs>=2.5.0 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from pooch->cdlib) (4.3.7) Requirement already satisfied: requests>=2.19.0 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from pooch->cdlib) (2.32.5) Requirement already satisfied: charset_normalizer<4,>=2 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from requests>=2.19.0->pooch->cdlib) (3.3.2) Requirement already satisfied: idna<4,>=2.5 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from requests>=2.19.0->pooch->cdlib) (3.7) Requirement already satisfied: urllib3<3,>=1.21.1 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from requests>=2.19.0->pooch->cdlib) (2.5.0) Requirement already satisfied: certifi>=2017.4.17 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from requests>=2.19.0->pooch->cdlib) (2025.10.5) Requirement already satisfied: Levenshtein==0.27.3 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from python-Levenshtein->cdlib) (0.27.3) Requirement already satisfied: rapidfuzz<4.0.0,>=3.9.0 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from Levenshtein==0.27.3->python-Levenshtein->cdlib) (3.14.3) Requirement already satisfied: joblib>=1.2.0 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from scikit-learn->cdlib) (1.5.2) Requirement already satisfied: threadpoolctl>=3.1.0 in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from scikit-learn->cdlib) (3.6.0) Requirement already satisfied: colorama in c:\users\mcr99\anaconda3\envs\axc-pac1\lib\site-packages (from tqdm->cdlib) (0.4.6)
# ----- Anàlisi descriptiu bàsic -----
from cdlib import algorithms # Llibreria per aplicar algorisme walktrap per la detecció de comunitats # Bibliografia: [Ref.9]
# Bibliografia: [Ref.2] --> Ús 1
socialization_nodes = socialization_graph.number_of_nodes() # Bibliografia: [Ref.3]
print(f"Nombre de nodes: {socialization_nodes}\n")
socialization_edges = socialization_graph.number_of_edges() # Bibliografia: [Ref.4]
print(f"Nombre de arestes: {socialization_edges}\n")
socialization_avg_degree = sum(dict(socialization_graph.degree()).values()) / socialization_nodes # Bibliografia: [Ref.5]
print(f"Grau mitjà dels nodes: {socialization_avg_degree}\n")
strengths_socialization = dict(socialization_graph.degree(weight="weight")) # Bibliografia
avg_strengt_socialization = sum(strengths_socialization.values()) / socialization_nodes
print(f"Average strength: {avg_strengt_socialization}\n")
weights_socialization = list(nx.get_edge_attributes(socialization_graph, "weight").values()) # Bibliografia: [Ref.6]
avg_weight_socialization = sum(weights_socialization) / len(weights_socialization)
print(f"Pes mitjà del graf: {avg_weight_socialization}\n")
socialization_connected = nx.number_connected_components(socialization_graph) # Bibliografia: [Ref.8]
print(f"Nombre de components connexes: {socialization_connected}\n")
average_clustering_socialization = nx.average_clustering(socialization_graph)
print(f"Coeficient de clustering promig: {average_clustering_socialization}\n")
walktrap_socialization = algorithms.walktrap(socialization_graph) # Bibliografia: [Ref.11]
number_communities_socialization = len(walktrap_socialization.communities) # Bibliografia: [Ref.10] i [Ref.2] --> Ús 2
print(f"Nombre de comunitats: {number_communities_socialization}\n")
communities_sizes_socialization = []
for community in walktrap_socialization.communities:
communities_sizes_socialization.append(len(community))
average_community_size_socialization = sum(communities_sizes_socialization) / len(communities_sizes_socialization)
print(f"Mida mitjana de les comunitats: {average_community_size_socialization}\n")
Note: to be able to use all crisp methods, you need to install some additional packages: {'leidenalg', 'graph_tool', 'infomap', 'bayanpy', 'wurlitzer'}
Note: to be able to use all crisp methods, you need to install some additional packages: {'ASLPAw', 'pyclustering'}
Note: to be able to use all crisp methods, you need to install some additional packages: {'wurlitzer', 'leidenalg', 'infomap'}
Nombre de nodes: 151
Nombre de arestes: 1554
Grau mitjà dels nodes: 20.582781456953644
Average strength: 25.00662251655629
Pes mitjà del graf: 1.214929214929215
Nombre de components connexes: 2
Coeficient de clustering promig: 0.7882579347214448
Nombre de comunitats: 17
Mida mitjana de les comunitats: 8.882352941176471
# ----- Visualització del graf -----
# Per evitar complicar massa la visualització, es prendrà com a representació del graf complet, la component màxima conectada
plt.figure(figsize=(30,30))
max_component = max(nx.connected_components(socialization_graph), key=len) # Bibliografia: [Ref.12]
max_subgraph = socialization_graph.subgraph(max_component) # Bibliografia: [Ref.13]
nx.draw(max_subgraph, pos=nx.spring_layout(max_subgraph)) # Bibliografia: [Ref.14]
plt.title("Graf d'interacció social dels dofins", fontsize=40) # Bibliografia: [Ref.15]
plt.show()
# ----- Lectura del csv i preparació de les arestes amb pesos -----
edges_weights_forage = [] # Per guardar tuples (node1, node2, pes)
with open("data/dolphin-florida-forage.csv") as f:
for line in f:
splitted_line = line.split(" ")
triple = (splitted_line[0].strip(), splitted_line[1].strip(), int(splitted_line[2].strip()))
edges_weights_forage.append(triple)
f.close()
# ----- Construcció del graf d'alimentació a partir de les arestes i els pesos anteriorment obtinguts del fitxer -----
forage_graph = nx.Graph()
forage_graph.add_weighted_edges_from(edges_weights_forage) # Bibliografia: [Ref.1]
# ----- Anàlisi descriptiu bàsic -----
from cdlib import algorithms # Llibreria per aplicar algorisme walktrap per la detecció de comunitats # Bibliografia: [Ref.9]
# Bibliografia: [Ref.2] --> Ús 1
forage_nodes = forage_graph.number_of_nodes() # Bibliografia: [Ref.3]
print(f"Nombre de nodes: {forage_nodes}\n")
forage_edges = forage_graph.number_of_edges() # Bibliografia: [Ref.4]
print(f"Nombre de arestes: {forage_edges}\n")
forage_avg_degree = sum(dict(forage_graph.degree()).values()) / forage_nodes # Bibliografia: [Ref.5]
print(f"Grau mitjà dels nodes: {forage_avg_degree}\n")
strengths_forage = dict(forage_graph.degree(weight="weight")) # Bibliografia
avg_strengt_forage = sum(strengths_forage.values()) / forage_nodes
print(f"Average strength: {avg_strengt_forage}\n")
weights_forage = list(nx.get_edge_attributes(forage_graph, "weight").values()) # Bibliografia: [Ref.6]
avg_weight_forage = sum(weights_forage) / len(weights_forage)
print(f"Pes mitjà del graf: {avg_weight_forage}\n")
forage_connected = nx.number_connected_components(forage_graph) # Bibliografia: [Ref.8]
print(f"Nombre de components connexes: {forage_connected}\n")
average_clustering_forage = nx.average_clustering(forage_graph)
print(f"Coeficient de clustering promig: {average_clustering_forage}\n")
walktrap_forage = algorithms.walktrap(forage_graph) # Bibliografia: [Ref.11]
number_communities_forage = len(walktrap_forage.communities) # Bibliografia: [Ref.10] i [Ref.2] --> Ús 2
print(f"Nombre de comunitats: {number_communities_forage}\n")
communities_sizes_forage = []
for community in walktrap_forage.communities:
communities_sizes_forage.append(len(community))
average_community_size_forage = sum(communities_sizes_forage) / len(communities_sizes_forage)
print(f"Mida mitjana de les comunitats: {average_community_size_forage}\n")
Nombre de nodes: 190 Nombre de arestes: 1134 Grau mitjà dels nodes: 11.936842105263159 Average strength: 13.884210526315789 Pes mitjà del graf: 1.1631393298059964 Nombre de components connexes: 6 Coeficient de clustering promig: 0.6587530358006516 Nombre de comunitats: 34 Mida mitjana de les comunitats: 5.588235294117647
# ----- Visualització del graf -----
# Per evitar complicar massa la visualització, es prendrà com a representació del graf complet, la component màxima conectada
plt.figure(figsize=(30,30))
max_component_forage = max(nx.connected_components(forage_graph), key=len) # Bibliografia: [Ref.12]
max_subgraph_forage = forage_graph.subgraph(max_component_forage) # Bibliografia: [Ref.13]
nx.draw(max_subgraph_forage, pos=nx.spring_layout(max_subgraph_forage)) # Bibliografia: [Ref.14]
plt.title("Graf d'alimentació dels dofins", fontsize=40) # Bibliografia: [Ref.15]
plt.show()
Referències externes:
[Ref.1] -- Graph.add_weighted_edges_from [en línia] [consulta:5 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/classes/generated/networkx.Graph.add_weighted_edges_from.html --> Documentació de la funció per a afegir arestes amb pes en un graf.
[Ref.2] -- OPENAI. ChatGPT [programari].GPT-5.2025
Ús 1 --> Utilitzat per saber quines son considerades mètriques bàsiques d'una anàlisi descriptiva d'un graf ponderat.
Ús 2 --> També s'ha utilitzat per comprovar una errata de la documentació de la funció walktrap() de la llibreria cdlib. Concretament en l'objecte de retorn. A la documentació consta NodeClusterint pero en realitat és NodeClustering
Ús 3 --> També s'ha utilitzat per obtenir una lectura fluïda de la resposta però deixant explicitament escrit que no es pot modificar les meves paraules, ja que si es fés ja no serien les meves paraules. En altres paraules, s'ha demanat a l'eina que ordeni la resposta per tal que sigui més facil de llegir.
Ús 4 --> També usada per saber com iterar de forma senzilla una llista on cada element es veu: (([t], [solution1,solution2,solution3]), beta) i no haver d'utilitzar excessius index en l'accés als elements. És a dir, per no haver d'accedir d'aquesta manera: sir_simulations[0][0][1][0][1]. Aquest accés donaria el primer I(t) de la primera beta
Ús 5 --> També utilitzada per saber si es pot aplicar la funció np.mean() a una llista de llistes.
Ús 6 --> També usada per saber perquè la crida a nx.louvain_partitions() no funciona directament. Com a resposta s'obté un import específic
Ús 7 --> També utilitzada per saber perquè la matriu de la partició que es retornava sempre era 1 a la primera comunitat i 0 a la resta. Com a resposta s'obté l'afegit de les toleràncies $1x10^{-12}$ en els càlculs del logaritme natural, abans de calcular la matriu inversa de Q i en les divisions de la matriu Q.
Ús 8 --> També utilitzada per saber com calcular la mètrica NMI tenint les dues matrius de partició. Com a resposta s'obté que s'ha de tornar a aplicar agrmax a les dues matrius.
[Ref.3] -- Graph.number_of_nodes [en línia] [consulta:5 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/classes/generated/networkx.Graph.number_of_nodes.html#networkx.Graph.number_of_nodes --> Documentació de la funció per saber el nombre de nodes del graf.
[Ref.4] -- Graph.number_of_edges [en línia] [consulta:5 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/classes/generated/networkx.Graph.number_of_edges.html#networkx.Graph.number_of_edges --> Documentació de la funció per saber el nombre d'arestes del graf.
[Ref.5] -- Graph.degree [en línia] [consulta:5 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/classes/generated/networkx.Graph.degree.html#networkx.Graph.degree --> Documentació de la funció per saber el grau dels nodes del graf.
[Ref.6] -- Notebook 2.2- Weighted and directed graphs [en línia] [consulta:5 de novembre de 2025]. Disponible a: https://transport-systems.imperial.ac.uk/tf/60008_21/n2_2_weighted_and_directed_graphs.html --> Conversa de StackOVerflow utilitzada per saber com obtenir els pesos del graf.
[Ref.7] -- is_connected [en línia] [consulta:5 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.is_connected.html --> Documentació de la funció per saber si el graf es connex.
[Ref.8] -- number_connected_components [en línia] [consulta:5 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.number_connected_components.html --> Documentació de la funció per saber el nombre de components connexes del graf.
[Ref.9] -- Community Detection Algorithms [en línia] [consulta:5 de novembre de 2025]. Disponible a: https://medium.com/data-science/community-detection-algorithms-9bd8951e7dae --> Web que explica diferents algorismes de detecció de comunitats i com aplicarlos en Python.
[Ref.10] -- Node Clustering [en línia] [consulta:5 de novembre de 2025]. Disponible a: https://cdlib.readthedocs.io/en/latest/reference/classes/node_clustering.html --> Documentació ofical de la definició de la classe. Un objecte d'aquesta es classe es retornat per la funció de la [Ref.9].
[Ref.11] -- cdlib.algorithms.walktrap [en línia] [consulta:5 de novembre de 2025]. Disponible a: https://cdlib.readthedocs.io/en/latest/reference/generated/cdlib.algorithms.walktrap.html#cdlib.algorithms.walktrap --> Documentació de la funció per aplicar l'algorisme walktrap.
[Ref.12] -- connected_components [en línia] [consulta:5 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.connected_components.html --> Documentació de la funció per a obtenir les components connexes d'un graf. En aquest cas s'ha obtingut la màxima component connexa.
[Ref.13] -- Graph.subgraph [en línia] [consulta:5 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/classes/generated/networkx.Graph.subgraph.html --> Documentació de la funció per a crear un subgraf d'un graf.
[Ref.14] -- draw [en línia] [consulta:5 de novembre de 2025]. Disponible a: https://networkx.org/documentation/networkx-1.10/reference/generated/networkx.drawing.nx_pylab.draw.html --> Documentació de la funció utilitzada per a printar el graf.
[Ref.15] -- matplotlib.pyplot.title [en línia] [consulta:5 de novembre de 2025]. Disponible a: https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.title.html --> Documentació de la funció utilitzada per saber com augmentar la mida de la lletra.
A continuació posarem el focus en els models epidèmics compartimentals. Com bé saps, aquests no només serveixen per modelar processos infecciosos biològics, sinó que també permeten explicar com es propaga un rumor o una idea en una determinada xarxa social.
Abans d’entrar en l’estudi d’un graf concret, començarem amb els models de camp mitjà, és a dir, aquells que s’apliquen sense graf. Les funcions que et mostrem a continuació permeten integrar de manera numèrica les equacions diferencials del model SIR en camp mitjà.
# Model SIR en camp mitjà suposan que el paràmetre K=1
def sir_meanfield_model(y, t, beta, gamma):
S, I, R = y
dS_dt = -beta * S * I
dI_dt = beta * S * I - gamma * I
dR_dt = gamma * I
return [dS_dt, dI_dt, dR_dt]
# Simulació
def sir_meanfield_simulation(S0, I0, R0, beta, gamma, days):
y0 = [S0, I0, R0]
t = np.linspace(0, days, days)
solution = odeint(sir_meanfield_model, y0, t, args=(beta, gamma))
return t, solution
La primera funció defineix el model compartimental SIR (Susceptible–Infectat–Recuperat) en camp mitjà. Calcula, en un pas de temps, la variació en el nombre d’individus en cada estat (dS/dt, dI/dt, dR/dt) donat el nombre actual de susceptibles, infectats i recuperats, i els paràmetres del virus: la probabilitat d’infecció β i la probabilitat de recuperació γ.
La segona funció realitza la integració del model fent servir odeint, un integrador numèric habitual de la llibreria scipy.integrate, basat en mètodes de pas adaptatiu. Pren com a paràmetres les condicions inicials (el percentatge inicial de susceptibles, infectats i recuperats), els paràmetres del virus i el temps màxim de la simulació. Retorna dos arrays: el pas del temps t (unidimensional) i el vector solució (tridimensional, amb les corbes d’evolució de S(t), I(t) i R(t)).
a) Genera una visualització de la progressió d’infectats per a diferents valors de β (Beta), tenint en compte que la probabilitat de recuperació γ és igual a 0,25, i interpreta-la. (1 punt)
Genera una animació que permeti observar l’evolució d’infectats i susceptibles per a un valor donat de β, comprès entre 0 i 1. (0,75 punts)
b) Implementa el model SIR en el graf d’interaccions socials de dofins, i repeteix la visualització del primer apartat mostrant la mitjana de 30 simulacions per a cada valor de β. Insereix un inset d’un graf Erdős–Rényi amb el mateix nombre de nodes i la mateixa densitat que el graf d’interaccions socials. (1 punt)
A continuació, genera una segona visualització que plasmi l’evolució de la desviació estàndard per als diferents valors de β obtinguts en cada tanda de 30 simulacions. Què observes? A què creus que es deuen aquests resultats? (0,75 punts)
c) Calcula els llindars epidèmics i els valors propis màxims dels dos grafs i raona el per què dels resultats. (0,5 punts)
Comentaris:
Per programar el model SIR en un graf en temps discret, inicialitza l’estat de cada node com a susceptible (S) o infectat (I), i crea una estructura per registrar l’evolució del nombre d’infectats a cada pas de temps. A cada pas de temps, cada node infectat pot contagiar els seus veïns susceptibles (els nodes connectats a ell) amb una probabilitat β (beta), i es pot recuperar (passar a l’estat R) amb una probabilitat γ (gamma). Actualitza els estats dels nodes a cada pas i registra el nombre d’infectats per analitzar l’evolució temporal de l’epidèmia.
Utilitza la llibreria numpy.random per obtenir nombres aleatoris i simular de manera estocàstica les transicions d’estat: de S a I en els veïns d’un node infectat, i de I a R en els nodes infectats.
# ---------- Apartat a ----------
# -- Condicions inicials (moment d'inici d'una epidèmia -- Molts susceptibles, pocs infects i cap recuperat) --
S0 = 0.99 # Susceptibles inicials (taxa) -- 99%
I0 = 0.01 # Infectats inicials (taxa) -- 1%
R0 = 0.00 # Recuperats inicials (taxa) -- 0%
# -- Simulació model SIR per cada beta amb les condicions inicials --
betas = np.arange(0, 1.05, 0.05) # Rang de betas de 0 a 1 amb step de 0.05
gamma = 0.25
sir_simulations = []
for beta in betas:
simulation = sir_meanfield_simulation(S0, I0, R0, beta, gamma, 100)
sir_simulations.append((simulation, beta))
plt.figure(figsize=(20,20))
for i, ((t, sols), betas) in enumerate(sir_simulations): # Bibliografia: [Ref.2] --> Ús 4
I = sols[:, 1] # Bibliografia: [Ref.16]
plt.plot(t, I, label=f"Beta: {round(betas, 2)}") # Bibliografia: [Ref.17]
plt.title("Gràfic d'evolució en el temps d'infectats per a diferents valors de beta", fontsize=15)
plt.xlabel("Moment en el temps (dia)", fontsize=15)
plt.ylabel("Taxa d'infectats I(t)", fontsize=15)
plt.locator_params(axis='x', nbins=20) # Bibliografia: [Ref.18]
plt.grid() # Bibliografia: [Ref.19]
plt.legend()
plt.show()
Comentari - Exercici 2 - Apartat a)
La visualització s'ha creat a partir d'un rang de probabilitats d'infecció β que van des de 0.0 a 1.0 amb un interval de 0.05. Les condicions inicials (R0, I0, S0) intenten recrear una situació el més real possible en l'inici d'una epidèmia. Per tant, es pren com a percentatge d'individus susceptibles a ser infectats el 99% de la població, l'1% de la població és la infectada i no hi ha cap individu recuperat (0%).
En el gràfic de l'evolució de la taxa d'infectats de la cèl·la anterior, on cada línia representa l'evolució de la taxa/percentatge d'infectats en el temps s'observa un canvi de comportament en les probabilitats β més elevades i les probabilitats β més petites.
Concretament, es pot observar que com més propera a 0 és la probabilitat β, més difícil és que la taxa d'infectats augmenti, de fet, per a probabilitats d'infecció β entre 0.0 i 0.25 la infecció no aconsegueix propagar-se, si no que ja comença disminuint. En canvi, com més augmenta la probabilitat d'infecció més ràpidament augmenta la taxa d'infectats, fins a arribar al pic de l'epidèmia. Aquest pic és més marcat a mesura que la probabilitat d'infecció es va apropant a 1 (i s'assoleix abans). També és un fet evident, observant el gràfic, que com més propera a 1 és la probabilitat d'infecció, més ràpidament decreix la taxa d'infectats.
# ---------- Animació ----------
from matplotlib.animation import FuncAnimation # Mòdul per crear animacions # Bibliografia: [Ref.20] i [Ref.21]
from IPython.display import HTML # Llibreria per renderitzar l'animació en aquest notebook
# -- Condicions inicials (moment d'inici d'una epidèmia -- Molts susceptibles, pocs infects i cap recuperat) --
beta_animation = 0.7
gamma_animation = 0.25
time = 50
S0 = 0.99 # Susceptibles inicials (taxa) -- 99%
I0 = 0.01 # Infectats inicials (taxa) -- 1%
R0 = 0.00 # Recuperats inicials (taxa) -- 0%
simulation_animation = sir_meanfield_simulation(S0, I0, R0, beta_animation, gamma_animation, time)
S = simulation_animation[1][:, 0] # Evolució susceptibles # Bibliografia: [Ref.16]
I = simulation_animation[1][:, 1] # Evolució infectats # Bibliografia: [Ref.16]
t = simulation_animation[0]
# -- Creació animació en base a [Ref.20] i [Ref.21]--
fig, ax = plt.subplots()
plt.title(f"Animació evolució S(t) i I(t) amb beta = {beta_animation} i gamma = {gamma_animation}", fontsize=12)
plt.xlabel("Moment en el temps (dia)")
plt.ylabel("Taxa")
graphic_infected, = ax.plot([], [], color='red', label='Taxa infectats')
graphic_susceptible, = ax.plot([], [], color='green', label='Taxa susceptibles')
ax.set_xlim(0, max(t))
ax.set_ylim(0, 1)
plt.legend()
def update(frame):
graphic_infected.set_data(t[:frame], I[:frame]) # Creació de les noves posicions de la taxa d'infectats
graphic_susceptible.set_data(t[:frame], S[:frame]) # Creació de les noves posicions de la taxa de susceptibles
return graphic_infected, graphic_susceptible
animation = FuncAnimation(fig, update, frames=len(t), blit=True)
animation.save("Animacio_exercici_2.gif", fps=60) # Bibliograia: [Ref.22]
plt.close() # Bibliografia: [Ref.23]
HTML(animation.to_jshtml()) # Bibliografia: [Ref.24]
MovieWriter ffmpeg unavailable; using Pillow instead.
# ---------- Apartat b ----------
socialization_density = nx.density(socialization_graph) # Densitat del graf de socialitzacio # Bibliografia: [Ref.25]
socialization_number_nodes = len(socialization_graph.nodes()) # Nombre de nodes del graf de socialització
erdos_renyi = nx.erdos_renyi_graph(socialization_number_nodes, socialization_density) # Bibliografia: [Ref.26]
# -- Condicions de simulacio --
betas_part_b = np.arange(0, 1.05, 0.05) # Rang de betas de 0 a 1 amb step de 0.05
gamma_part_b = 0.25
simulations_per_beta = 30
def SIR_over_socialization_dolphin(graph, beta, gamma, days):
# -- Condicions inicials: 1% infectats i 99% susceptibles --
num_initial_infected = int(len(graph.nodes) / 100) # Dona quants dofins s'han d'infectar en l'inici per tenir un 1% d'infectats
dolphins_initial_infected = np.random.choice(graph.nodes(), num_initial_infected, replace=False) # Bibliografia: [Ref.27]
# -- Inicialització de simulació amb pocs infectats i molts susceptibles - Assignació d'estat inicial --
dolphins_health = {}
for dolphin in graph.nodes():
if dolphin in dolphins_initial_infected:
dolphins_health[dolphin] = "Infected"
else:
dolphins_health[dolphin] = "Susceptible"
# -- Evolució epidèmia en el temps (paràmetre days) --
percentage_infected_every_day = [] # Per guardar el percentatge de dofins infectats al llarg dels dies
infected = num_initial_infected # Nombre de dofins infectats -- Comença amb l'1%
for day in range(days):
for dolphin in graph.nodes():
if dolphins_health[dolphin] == "Infected": # Els infectats poden contagiar els seus veins
neighbors = nx.all_neighbors(graph, dolphin) # Obtenció dels veins del node # Bibliografia: [Ref.28]
for neighbor in neighbors:
if dolphins_health[neighbor] == "Susceptible" and np.random.random() < beta: # Bibliografia: [Ref.29]
dolphins_health[neighbor] = "Infected" # Si el vei es susceptible i el random cau dins la probabilitat --> Infectat
infected += 1 # Si s'infecta el dofí -- Un dofi més que hi ha infectat
if np.random.random() < gamma:
dolphins_health[dolphin] = "Recovered" # Amb probabilitat gamma el dofi es recupera
infected -= 1 # Si el dofi es recupera hi ha un dofi menys infectat
percentage_infected_every_day.append(infected / len(graph.nodes))
return percentage_infected_every_day
# -- 30 repeticions per beta --
means_per_beta = {} # Per guardar la mitjana de les 30 execucions per cada beta
days = 50
for beta in betas_part_b:
simulations_results = [] # Per guardar els resultats d'una beta concreta al llarg de les 30 simulacions
for num_simulation in range(simulations_per_beta):
simulation = SIR_over_socialization_dolphin(socialization_graph, beta, gamma_part_b, days)
simulations_results.append(simulation)
means_per_beta[beta] = np.mean(simulations_results, axis=0) # Bibliografia: [Ref.2] --> Ús 5
fig = plt.figure(figsize=(20,20))
# -- Printar les corbes de cada beta --
for beta, infected_percentage in means_per_beta.items():
plt.plot(range(days), infected_percentage, label=f"Beta = {round(beta,2)}")
plt.legend()
plt.title("Gràfic d'evolució en el temps (50 dies) de la mitjana de la taxa de dofins infectats per cada beta (30 simulacions per beta)", fontsize=20)
plt.xlabel("Moment en el temps (dia)", fontsize=15)
plt.ylabel("Taxa d'infectats I(t) (mitjana de 30 simulacions)", fontsize=15)
plt.locator_params(axis='x', nbins=20) # Bibliografia: [Ref.18]
plt.grid() # Bibliografia: [Ref.19]
# -- Inset -- # Bibliografia: [Ref.30]
left, bottom, width, height = [0.25, 0.15, 0.7, 0.7]
ax2 = fig.add_axes([left, bottom, width, height]) # Bibliografia: [Ref.31]
nx.draw(erdos_renyi, node_size=80, ax=ax2) # Bibliografia: [Ref.32] i [Ref.33]
ax2.set_title("Inset Erdős–Rényi", fontsize=20) # Bibliografia: [Ref.34]
plt.show()
# -- Calcul de desviacions per cada beta --
std_per_beta = {} # Per guardar la mitjana de les 30 execucions per cada beta
days = 50
for beta in betas_part_b:
simulations_results = [] # Per guardar els resultats d'una beta concreta al llarg de les 30 simulacions
for num_simulation in range(simulations_per_beta):
simulation = SIR_over_socialization_dolphin(socialization_graph, beta, gamma_part_b, days)
simulations_results.append(simulation)
std_per_beta[beta] = np.std(simulations_results, axis=0) # Guardar la desviacio
std_per_beta
{0.0: array([0.00264901, 0.00330389, 0.00319135, 0.00303482, 0.00246807,
0.00165195, 0.00118878, 0.00118878, 0.00118878, 0.00118878,
0.00118878, 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.05: array([0.01255758, 0.05863037, 0.11854613, 0.15499597, 0.15232364,
0.14915698, 0.13665868, 0.12660078, 0.11816981, 0.11357932,
0.10668466, 0.094498 , 0.09132805, 0.07476766, 0.06290771,
0.04736064, 0.04066906, 0.03054744, 0.0244635 , 0.01908695,
0.01392829, 0.01096888, 0.00853822, 0.0079009 , 0.00672837,
0.00560637, 0.00532096, 0.00501449, 0.00388044, 0.00300253,
0.00165195, 0.00118878, 0.00118878, 0.00118878, 0.00118878,
0.00118878, 0.00118878, 0.00118878, 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.1: array([0.06780636, 0.17027925, 0.19079234, 0.19578272, 0.16926314,
0.16429893, 0.14922084, 0.12474672, 0.10012467, 0.07947173,
0.05909398, 0.04579709, 0.0352296 , 0.02703271, 0.02364093,
0.01805437, 0.01426534, 0.01066936, 0.01050364, 0.00932393,
0.0094408 , 0.00906153, 0.00696677, 0.00698423, 0.00586133,
0.00473972, 0.00328169, 0.00246807, 0.00165195, 0.00165195,
0.00165195, 0.00165195, 0.00165195, 0.00165195, 0.00165195,
0.00118878, 0.00118878, 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.15000000000000002: array([0.13052687, 0.19404262, 0.17146564, 0.10208633, 0.09296613,
0.0888789 , 0.09073492, 0.09634162, 0.07620851, 0.05930594,
0.05403701, 0.04410815, 0.03590574, 0.02571057, 0.02252197,
0.01907801, 0.01555469, 0.01351635, 0.01179725, 0.01028091,
0.00759587, 0.00538921, 0.00407642, 0.00370045, 0.00348338,
0.00328169, 0.00246807, 0.00246807, 0.00225122, 0.00198675,
0.00165195, 0.00118878, 0.00118878, 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.2: array([0.20946203, 0.21639455, 0.17065831, 0.11089173, 0.110837 ,
0.09396405, 0.07537557, 0.05914467, 0.04965121, 0.0414876 ,
0.03177658, 0.02373043, 0.01984423, 0.01597966, 0.01383703,
0.01129069, 0.00856387, 0.00732147, 0.00650746, 0.00570972,
0.00505803, 0.00471394, 0.00435388, 0.00348338, 0.00339123,
0.00300253, 0.00300253, 0.00282699, 0.00282699, 0.00198675,
0.00118878, 0.00118878, 0.00118878, 0.00118878, 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.25: array([0.22967183, 0.25603029, 0.1900784 , 0.16726658, 0.13762606,
0.11017664, 0.08679765, 0.07095542, 0.0524667 , 0.04284153,
0.03188604, 0.02682732, 0.02110565, 0.01649732, 0.01452431,
0.01201216, 0.01073311, 0.00860927, 0.00671024, 0.00606964,
0.00560202, 0.00435388, 0.00379794, 0.00358677, 0.00198675,
0.00165195, 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.30000000000000004: array([0.24345533, 0.19511702, 0.11734797, 0.11430616, 0.09643136,
0.07375976, 0.05719144, 0.04617065, 0.0339669 , 0.03096494,
0.02576737, 0.02106404, 0.01733138, 0.01352897, 0.01036353,
0.0099705 , 0.00899677, 0.00639796, 0.00511074, 0.00407642,
0.00394891, 0.00379794, 0.00315295, 0.00246807, 0.00225122,
0.00198675, 0.00198675, 0.00198675, 0.00198675, 0.00165195,
0.00165195, 0.00118878, 0.00118878, 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.35000000000000003: array([0.24885354, 0.2213952 , 0.16430738, 0.13872008, 0.11004122,
0.08372356, 0.06581958, 0.04729217, 0.03621991, 0.02665969,
0.0215941 , 0.01868051, 0.01555313, 0.01267347, 0.00973307,
0.00759908, 0.00740091, 0.00683971, 0.00442053, 0.0035595 ,
0.00339123, 0.00225122, 0.00225122, 0.00225122, 0.00198675,
0.00198675, 0.00165195, 0.00118878, 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.4: array([0.27845002, 0.13318066, 0.11220471, 0.09098565, 0.07551605,
0.06214824, 0.05231788, 0.0439931 , 0.03251559, 0.02752663,
0.0247841 , 0.01984423, 0.0146579 , 0.01196134, 0.0103282 ,
0.00861776, 0.00713267, 0.00608968, 0.0055364 , 0.00538921,
0.00471394, 0.00348338, 0.00264901, 0.00225122, 0.00225122,
0.00198675, 0.00198675, 0.00198675, 0.00198675, 0.00198675,
0.00165195, 0.00165195, 0.00118878, 0.00118878, 0.00118878,
0.00118878, 0.00118878, 0.00118878, 0.00118878, 0.00118878,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.45: array([0.26887417, 0.13073652, 0.08850969, 0.08130126, 0.06192397,
0.05378754, 0.04404458, 0.03345227, 0.02232093, 0.02191999,
0.0196406 , 0.01883508, 0.01681331, 0.01238763, 0.01165805,
0.01030695, 0.00748276, 0.00558896, 0.00356633, 0.00339123,
0.0037267 , 0.00362058, 0.00339123, 0.00315295, 0.00315295,
0.00198675, 0.00198675, 0.00198675, 0.00198675, 0.00118878,
0.00118878, 0.00118878, 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.5: array([0.26981425, 0.06875414, 0.07690741, 0.06711724, 0.05498816,
0.04137468, 0.03256725, 0.02712718, 0.02471618, 0.02232093,
0.0199703 , 0.01744488, 0.01687118, 0.01427387, 0.01285102,
0.01208294, 0.00906153, 0.00857524, 0.00764702, 0.00596026,
0.0058238 , 0.00560637, 0.00471394, 0.00407642, 0.00385524,
0.00237756, 0.00237756, 0.00118878, 0.00118878, 0.00118878,
0.00118878, 0.00118878, 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.55: array([0.27913285, 0.16177341, 0.13009982, 0.10113749, 0.079912 ,
0.0684857 , 0.05292307, 0.04020812, 0.03259642, 0.02527473,
0.0206564 , 0.0193821 , 0.01685384, 0.01272718, 0.01193075,
0.01053144, 0.00699469, 0.00625936, 0.00529801, 0.00439288,
0.00328169, 0.00315295, 0.00225122, 0.00118878, 0.00118878,
0.00118878, 0.00118878, 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.6000000000000001: array([0.25981843, 0.06212824, 0.06562829, 0.05490657, 0.04205863,
0.03942484, 0.03511322, 0.03308976, 0.02607848, 0.02273195,
0.02028504, 0.01817677, 0.01488062, 0.01317124, 0.00947943,
0.00866569, 0.00596026, 0.00616523, 0.00620069, 0.00533468,
0.00505321, 0.00471394, 0.00315295, 0.00165195, 0.00118878,
0.00118878, 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.65: array([0.23889749, 0.0574291 , 0.05995969, 0.04914812, 0.03915507,
0.03114383, 0.03206967, 0.02356557, 0.02759294, 0.02185765,
0.01670864, 0.01284154, 0.00870776, 0.00632519, 0.00634058,
0.00694225, 0.0063059 , 0.00624767, 0.00551435, 0.00409431,
0.00410026, 0.00366738, 0.0035595 , 0.00328169, 0.00246807,
0.00225122, 0.00225122, 0.00198675, 0.00198675, 0.00165195,
0.00118878, 0.00118878, 0.00118878, 0.00118878, 0.00118878,
0.00118878, 0.00118878, 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.7000000000000001: array([0.27948354, 0.08070569, 0.0832496 , 0.06933114, 0.0609963 ,
0.05227688, 0.04411091, 0.03711302, 0.02847939, 0.02832927,
0.02311143, 0.02133871, 0.0182156 , 0.01468282, 0.01421229,
0.01193687, 0.0096728 , 0.0078638 , 0.00712241, 0.00585717,
0.00604147, 0.00560202, 0.00370045, 0.00362058, 0.00362058,
0.00292859, 0.00292859, 0.00264901, 0.00225122, 0.00165195,
0.00165195, 0.00165195, 0.00118878, 0.00118878, 0.00118878,
0.00118878, 0.00118878, 0.00118878, 0.00118878, 0.00118878,
0.00118878, 0.00118878, 0.00118878, 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.75: array([0.27000455, 0.06262044, 0.0681987 , 0.05609367, 0.05219992,
0.04716835, 0.04278007, 0.03469086, 0.02847597, 0.02362753,
0.02090614, 0.01601164, 0.01529405, 0.01281304, 0.01198779,
0.00910446, 0.00846082, 0.00662252, 0.00370045, 0.00330389,
0.00312188, 0.00303482, 0.00225122, 0.00165195, 0.00165195,
0.00165195, 0.00118878, 0.00118878, 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.8: array([0.27842202, 0.13529326, 0.1189442 , 0.09119991, 0.067188 ,
0.05032386, 0.04052682, 0.0339877 , 0.02940626, 0.02572478,
0.0187261 , 0.01400505, 0.01174136, 0.01205872, 0.01036353,
0.00911248, 0.00849531, 0.00771364, 0.00656339, 0.00503873,
0.00366738, 0.00348338, 0.00280101, 0.00225122, 0.00165195,
0.00165195, 0.00165195, 0.00118878, 0.00118878, 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.8500000000000001: array([0.27931889, 0.06003482, 0.07376372, 0.06750384, 0.05703786,
0.0501648 , 0.04289667, 0.03713862, 0.02954183, 0.02634619,
0.02283888, 0.0187625 , 0.01438101, 0.01153197, 0.00907228,
0.0091658 , 0.00698423, 0.00650746, 0.00532096, 0.00409431,
0.00407642, 0.00404642, 0.00292859, 0.00264901, 0.00225122,
0.00118878, 0.00118878, 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.9: array([0.27141871, 0.17583291, 0.15284868, 0.1197266 , 0.0999042 ,
0.07807333, 0.06008958, 0.04973946, 0.0402372 , 0.03223563,
0.02941537, 0.02083609, 0.01698632, 0.01287943, 0.00987226,
0.00719051, 0.00748276, 0.00682544, 0.00542975, 0.00503873,
0.00475511, 0.00312188, 0.00264901, 0.00246807, 0.00246807,
0.00198675, 0.00118878, 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
0.9500000000000001: array([0.27624892, 0.13432612, 0.11584862, 0.09653263, 0.07675805,
0.06430665, 0.05218732, 0.04200066, 0.03626025, 0.02592856,
0.02070353, 0.01455783, 0.01394228, 0.01356494, 0.01077842,
0.00927152, 0.00814387, 0.00843775, 0.00703637, 0.00558896,
0.00532096, 0.00471394, 0.00400405, 0.00388044, 0.00388044,
0.00358677, 0.00282699, 0.00282699, 0.00118878, 0.00118878,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ]),
1.0: array([0.2711551 , 0.13477811, 0.12809259, 0.10435596, 0.08384715,
0.06302844, 0.0516594 , 0.04074089, 0.0307953 , 0.02525545,
0.02020923, 0.01906779, 0.01467784, 0.01394228, 0.0127883 ,
0.01365088, 0.01255758, 0.01117792, 0.0072546 , 0.00501449,
0.00443703, 0.0035595 , 0.00339123, 0.00328169, 0.00246807,
0.00225122, 0.00165195, 0.00118878, 0.00118878, 0.00118878,
0.00118878, 0.00118878, 0.00118878, 0.00118878, 0.00118878,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ])}
plt.figure(figsize=(20,20))
for beta, std in std_per_beta.items():
plt.plot(range(days), std, label=f"Beta = {round(beta,2)}")
plt.title("Evolució de la desviació standard en 30 simulacions per beta", fontsize=20)
plt.xlabel("Moment en el temps (dia)", fontsize=15)
plt.ylabel("Desviació stnadard", fontsize=15)
plt.locator_params(axis='x', nbins=20) # Bibliografia: [Ref.18]
plt.grid() # Bibliografia: [Ref.19]
plt.legend()
plt.show()
El primer que es pot observar en el gràfic de les desviacions és, que per a tot valor de β, la desviació es més elevada durant els primers dies i que a mesura que avança el temps (i un cop es passa el pic de l'epidèmia), la desviació decau fins a arribar a 0.
També es pot observar que la desviació tendeix a ser mes elevada amb valors de β grans.
Finalment, es pot observar que per als valors de β mes elevats, el pic de desivació és molt elevat però molt curt.
Per tant, es pot concloure que el valor de β té un impacte important en les desviacions.
A que es deu?
L'elevada desviació els primers dies es deu a que durant les primeres jornades de l'epidèmia les 30 simulacions de cada beta tenen resultats força difernts, ja que, la taxa de dofins infectats de cada dia es molt diferent entre aquestes 30 simulacions.
En canvi, com mes disminueix la desviació, més a prop estan els valors de la taxa d'infectats al llarg de les 30 simulacions de cada beta. És a dir, a mesura que la epidèmia avança, la taxa d'infectats es comença a estabilitzar (es començen a apropar-se) en les 30 simulacions fins que acaba completament estabilitzat (desviació 0).
# -- Calcul valors propis màxims --
# Bibliografia: [Ref.35]
adjacency_matrix_erdos = nx.adjacency_matrix(erdos_renyi) # Bibliografia: [Ref.36]
adjacency_matrix_dolphins = nx.adjacency_matrix(socialization_graph, weight='weight')
array_adjacency_erdos = adjacency_matrix_erdos.toarray() # Bibliografia: [Ref.37] i [Ref.38]
array_adjacency_dolphins = adjacency_matrix_dolphins.toarray() # toarray() es de SciPy -- Importat amb llibreries basiques de la PAC
eigenvalues_erdos, eigenvectors_erdos = np.linalg.eig(array_adjacency_erdos) # Bibliografia: [Ref.39]
eigenvalues_dolphins, eigenvectors_dolphins = np.linalg.eig(array_adjacency_dolphins)
max_eigvenval_dolphins = max(eigenvalues_dolphins)
max_eigenval_erdos = max(eigenvalues_erdos)
print(f"Valor propi màxim del graf de socialització dels dofins: {max_eigvenval_dolphins}\n")
print(f"Valor propi màxim del graf d'Erdos-Renyi: {max_eigenval_erdos}\n")
# -- Calcul llindars epidemics --
# Bibliografia: [Ref.35],[Ref.40],[Ref.41] i [Ref.42]
llindar_erdos = gamma / max_eigenval_erdos
llindar_dolphins = gamma / max_eigvenval_dolphins
print(f"Llindar epidèmic graf de socialització: {llindar_dolphins}\n")
print(f"Llindar epidèmic graf d'Erdos-Renyi: {llindar_erdos}")
Valor propi màxim del graf de socialització dels dofins: 53.707634879337874 Valor propi màxim del graf d'Erdos-Renyi: 21.568572079406938 Llindar epidèmic graf de socialització: 0.0046548316745219165 Llindar epidèmic graf d'Erdos-Renyi: 0.01159093884748601
Raonament apartat c:
El màxim eigenvalue del graf de socialització, és molt major al del graf d'Erdos, per tant, atenent a la fórmula presentada en l'apartat 3.2.2 del material docent ([Ref.42]), es pot deduir que el llindar epidèmic serà major per al graf d'Erdos. És a dir en el graf de socialització serà necessàri un valor menor de la probabilitat d'infecció β per a que l'epidèmia s'expandeixi.
[Ref.16] -- Python slicing multi-dimensional arrays [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://www.geeksforgeeks.org/python/python-slicing-multi-dimensional-arrays/ --> Utilitzat per saber com fer slicing en una array que conté múltiples arrays.
[Ref.17] -- matplotlib.pyplot.plot [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.plot.html --> Documentació de la funció per a crear un gràfic de linies.
[Ref.18] -- Matplotlib.pyplot.locator_params() in Python [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://www.geeksforgeeks.org/python/matplotlib-pyplot-locator_params-in-python/ --> Web utilitzada per saber com controlar el comportament de les etiquetes dels eixos.
[Ref.19] -- Matplotlib Adding Grid Lines [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://www.w3schools.com/python/matplotlib_grid.asp --> Web utilitzada per saber com inserir les línies de graella de cada valor dels eixos.
[Ref.20] -- Animaciones con Matplotlib [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://www.pypro.mx/app/curso/graficos-con-matplotlib/animaciones-con-matplotlib --> Tutorial de creació d'una animació amb Matplotlib.
[Ref.21] -- Tutorial de Animación en Matplotlib - Crea Visualizaciones Impresionantes [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://docs.kanaries.net/es/topics/Matplotlib/matplotlib-animation Tutorial de creació d'animacions amb Matplotlib. En aquesta web s'ha revisat les seccions Guardar tu Animación en Matplotlib i Animación de múltiples subgráficos con Matplotlib
[Ref.22] -- matplotlib save animation in gif error [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://stackoverflow.com/questions/25140952/matplotlib-save-animation-in-gif-error --> Conversa d'StackOverflow usada per a saber com guardar l'animació en un fitxer.
[Ref.23] -- Calling pylab.savefig without display in ipython [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://stackoverflow.com/questions/15713279/calling-pylab-savefig-without-display-in-ipython --> Conversa d'StackOverflow usada per saber com no printar el gràfic de matplotlib.
[Ref.24] -- Inline animations in Jupyter [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://stackoverflow.com/questions/43445103/inline-animations-in-jupyter --> Conversa d'StackOverflow usada per saber com poder visualitzar l'animació en un notebook de Jupyter.
[Ref.25] -- density [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/generated/networkx.classes.function.density.html --> Documentació de la funció per a obtenir la densitat d'un graf.
[Ref.26] -- erdos_renyi_graph [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/generated/networkx.generators.random_graphs.erdos_renyi_graph.html --> Documentació de la funció per a crear un graf Erdos-Rényi.
[Ref.27] -- numpy.random.choice [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://numpy.org/doc/stable/reference/random/generated/numpy.random.choice.html --> Documentació de la funció per a escollir 1 o més elements de manera aleatòria d'una array.
[Ref.28] -- all_neighbors [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/generated/networkx.classes.function.all_neighbors.html --> Documentació de la funció par a obtenir els veins d'un node.
[Ref.29] -- Generate Random Float Number in Python [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://www.geeksforgeeks.org/python/python-generate-random-float-number/ --> Web que explica com generar floats aleatòris amb la llibreria numpy i amb la llibreria random.
[Ref.30] -- How to add different graphs (as an inset) in another python graph [duplicate] [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://stackoverflow.com/questions/21001088/how-to-add-different-graphs-as-an-inset-in-another-python-graph --> Conversa d'StackOverflow que enseña com afegir un inset.
[Ref.31] -- matplotlib.figure.Figure.add_axes [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://matplotlib.org/stable/api/_as_gen/matplotlib.figure.Figure.add_axes.html --> Documentació de la funció per a afegir eixos a una figura.
[Ref.32] -- draw [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://networkx.org/documentation/networkx-1.10/reference/generated/networkx.drawing.nx_pylab.draw.html --> Documentació de la funció per dibuixar grafs.
[Ref.33] -- draw_networkx [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/generated/networkx.drawing.nx_pylab.draw_networkx.html --> Documentació de les optional keywords que es poden definir en les crides a draw().
[Ref.34] -- matplotlib.axes.Axes.set_title [en línia] [consulta:8 de novembre de 2025]. Disponible a: https://matplotlib.org/stable/api/_as_gen/matplotlib.axes.Axes.set_title.html#matplotlib.axes.Axes.set_title --> Documentació de la funció per afegir un títol a un eix concret de la figura.
[Ref.35] -- Graph Eigenvalue [en línia] [consulta:11 de novembre de 2025]. Disponible a: https://mathworld.wolfram.com/GraphEigenvalue.html --> Web que explica que són els valors propis d'un graf.
[Ref.36] -- adjacency_matrix [en línia] [consulta:11 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/generated/networkx.linalg.graphmatrix.adjacency_matrix.html --> Documentació de la funció per obtenir la matriu d'adjacència d'un graf.
[Ref.37] -- How do I transform a "SciPy sparse matrix" to a "NumPy matrix"? [en línia] [consulta:11 de novembre de 2025]. Disponible a: https://stackoverflow.com/questions/26576524/how-do-i-transform-a-scipy-sparse-matrix-to-a-numpy-matrix --> Conversa d'StackOverflow que explica com converitr una sparse matrix de SciPy a una matriu de NumPy.
[Ref.38] -- toarray [en línia] [consulta:11 de novembre de 2025]. Disponible a: https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csr_matrix.toarray.html --> Documentació de la funció que transforma una sparse matrix a una ndarray.
[Ref.39] -- numpy.linalg.eig [en línia] [consulta:11 de novembre de 2025]. Disponible a: https://numpy.org/doc/2.1/reference/generated/numpy.linalg.eig.html --> Documentació de la funció per a calcular els valros i vectors propis d'una matriu.
[Ref.40] -- Spectral Radius [en línia] [consulta:11 de novembre de 2025]. Disponible a: https://mathworld.wolfram.com/SpectralRadius.html --> Web que explica que és el radi espectral d'una matriu. En la [Ref.35], es relaciona el valor màxim propi amb aquest concepte.
[Ref.41] -- Spectral Radius [en línia] [consulta:11 de novembre de 2025]. Disponible a: https://www.sciencedirect.com/topics/mathematics/spectral-radius#definition --> Web que explica característiques del radi espectral, entre les quals hi ha una definició "family friendly" del radi espectral.(Aquesta definició, segons els web, ha estat generada amb IA).
[Ref.42] -- AROLA FERNÁNDEZ, Lluís. Difusió i propagació de la informació [en línia]. Barcelona, UOC, 2023 [consulta:11 de novembre de 2025]. Disponible a: https://aprenentatge.recursos.uoc.edu/continguts/pdf/PID_00286319.pdf --> Recurs PDF de l'assignatura on s'explica que es el llindar epidèmic.
En aquest exercici, i seguint amb l’article que estudia la interacció entre dofins, passem a estudiar com s’estructuren en comunitats. Som-hi:
a) Començarem aplicant l’algoritme de Girvan–Newman als grafs d’interaccions socials i d’alimentació. Cal que l’apliquis als nivells que consideris necessaris, obtenint per a cada nivell la modularitat i el percentatge de nodes de la comunitat més gran. Fes una visualització senzilla en què es mostri com varia la modularitat a mesura que augmenten les comunitats detectades, i interpreta els resultats relacionant-los amb l’article en qüestió. (1,25 punts)
b) Queda’t amb el graf amb la modularitat més alta obtinguda, i aplica un altre algoritme de detecció de comunitats que pugui ser comparable amb l’anterior; fes una visualització simple dels resultats i determina quin és més òptim en termes de modularitat, cost computacional, etc. (0,5 punts)
c) Realitza una visualització avançada dels dos grafs mitjançant la qual es destaquin aspectes rellevants tant a nivell de nodes i arestes com a nivell de comunitats, que permetin la comprensió de l’estructura morfològica d’aquestes dues xarxes. Per fer-les pots utilitzar la llibreria de Python que consideris necessària o bé un programa extern com Gephi (https://gephi.org/ o https://lite.gephi.org). En qualsevol cas, et demanem que generis un PDF que contingui les dues visualitzacions, així com un petit informe amb l’explicació que consideris necessària per a la plena comprensió (per exemple, els algoritmes utilitzats, els paràmetres destacats a nivell de node, d’aresta, etc.). (1,5 punts)
# -- Definició d'una funció que apliqui Girvan-Newman i obtingui per cada nivell la modularitat i el percentatge de nodes
def data_girvan_newman(graph):
girvan_newman_algorithm = nx.community.girvan_newman(graph) # Bibliografia: [Ref.42]
graph_nodes = graph.nodes()
results = [] # Guardar (modularitat, % nodes major comunitat, nombre comunitats)
for level in range(20): # 15 nivells
level_data = next(girvan_newman_algorithm) # Aqui hi ha: tuple(set(), set(), set()...) d'un nivell # Bibliografia: [Ref.43]
# -- Deteccio comunitats --
communities = []
for elem in level_data:
communities.append(elem)
num_communities = len(communities)
biggest_community = max(communities, key=len) # Bibliografia: [Ref.44]
# -- Modularitat --
modularity = nx.community.modularity(graph, communities, weight='weight') # Bibliografia: [Ref.45]
# -- Percentatge de nodes de la comunitat més gran --
percentage = (len(biggest_community) / len(graph_nodes)) * 100
result_to_append = (modularity, percentage, num_communities)
results.append(result_to_append)
return results
info_graph_socialization = data_girvan_newman(socialization_graph)
info_graph_forage = data_girvan_newman(forage_graph)
print("Dades del graf de socialització en format (modularitat, % nodes major comunitat, nombre comunitats).\nCada element de la llista, " +
f"és un nivell de l'algorisme Girvan-Newman.\n{info_graph_socialization}\n")
print("-------------------------------------------------------------------------------------------")
print("Dades del graf d'alimentació en format (modularitat, % nodes major comunitat, nombre comunitats).\nCada element de la llista, " +
f"és un nivell de l'algorisme Girvan-Newman.\n{info_graph_forage}\n")
Dades del graf de socialització en format (modularitat, % nodes major comunitat, nombre comunitats). Cada element de la llista, és un nivell de l'algorisme Girvan-Newman. [(0.00422284028476007, 96.68874172185431, 3), (0.03281415519067788, 91.3907284768212, 4), (0.03278750381535473, 90.72847682119205, 5), (0.06199516684322029, 85.43046357615894, 6), (0.067726615241669, 83.44370860927152, 7), (0.0809348965814421, 80.13245033112582, 8), (0.08612742611677672, 77.48344370860927, 9), (0.08783086981111743, 76.15894039735099, 10), (0.08863602188667043, 74.83443708609272, 11), (0.1209913526106004, 69.5364238410596, 12), (0.12129209234056298, 68.87417218543047, 13), (0.1210609267272335, 68.21192052980133, 14), (0.12070912857296753, 67.54966887417218, 15), (0.1208819417013789, 66.88741721854305, 16), (0.12052004407856926, 66.22516556291392, 17), (0.12068275773843727, 65.56291390728477, 18), (0.14813690054043374, 59.60264900662252, 19), (0.1616648581136885, 56.29139072847682, 20), (0.16165335594118077, 55.62913907284768, 21), (0.16263272384910946, 54.966887417218544, 22)] ------------------------------------------------------------------------------------------- Dades del graf d'alimentació en format (modularitat, % nodes major comunitat, nombre comunitats). Cada element de la llista, és un nivell de l'algorisme Girvan-Newman. [(0.02702468902337742, 91.05263157894737, 7), (0.041648536781776324, 87.36842105263159, 8), (0.05248968105389186, 83.6842105263158, 9), (0.08066797680830864, 79.47368421052632, 10), (0.08201758747322188, 78.42105263157895, 11), (0.08197562768679144, 77.89473684210526, 12), (0.08189055853074072, 77.36842105263158, 13), (0.08184773655691789, 76.84210526315789, 14), (0.08180462718729747, 76.31578947368422, 15), (0.08176123042187979, 75.78947368421053, 16), (0.08171754626066449, 75.26315789473685, 17), (0.08438228009479459, 73.68421052631578, 18), (0.0857100486791002, 72.63157894736842, 19), (0.08703321893064625, 71.57894736842105, 20), (0.13532778352888694, 65.26315789473685, 21), (0.14387263537922734, 62.63157894736842, 22), (0.15142166079133848, 61.05263157894737, 23), (0.1583760642984869, 58.94736842105262, 24), (0.16270194584198633, 57.36842105263158, 25), (0.16228809589363127, 56.84210526315789, 26)]
# -- Visualització graf socialització --
data_x_socialization = [] # Nombre de comunitats
data_y_socialization = [] # Modularitats
for mod, percentage, num_coms in info_graph_socialization:
data_x_socialization.append(num_coms)
data_y_socialization.append(mod)
data_x_forage = [] # Nombre de comunitats
data_y_forage = [] # Modularitats
for mod, percentage, num_coms in info_graph_forage:
data_x_forage.append(num_coms)
data_y_forage.append(mod)
plt.figure(figsize=(20,20))
plt.plot(data_x_socialization, data_y_socialization, label="Socialització")
plt.plot(data_x_forage, data_y_forage, label="Alimentació")
plt.legend()
plt.locator_params(axis='x', nbins=20) # Bibliografia: [Ref.18]
plt.locator_params(axis='y', nbins=20) # Bibliografia: [Ref.18]
plt.title("Evolució de la modularitat a mesura que augmenten les el nombre de comunitats", fontsize=20)
plt.ylabel("Modularitat", fontsize=15)
plt.xlabel("Nombre de comunitats", fontsize=15)
plt.grid()
plt.show()
Interpretació gràfics apartat a)
Es pot observar que la modularitat del graf d'alimentació comença amb un major nombre de comunitats, ja que el graf d'alimentació té més comunitats que el graf de socialització.
Una aspecte molt important és que la modularitat del graf de socialització és major que la del graf d'alimentació. Aquest fet suggerix que els nodes de cada comunitat estàn molt interconnectats entre ells però que tenen poques connexions amb altres comunitats. En la xarxa d'alimentació passa el contrari, una modularitat menor, suggereix que els nodes de les comunitats no estàn tant interconnectats entre ells. Per tant, en base als resultats de l'estudi de la modularitat, les comunitats de la xarxa de socialització estàn millor definides internament (els nodes de cada comunitat estan més interconnectats entre ells que en la xarxa d'alimentació).
# Bibliografia: [Ref.46]
# Graf amb major modularitat -> Socialització
# Elecció del segon algorisme --> [Ref.47]
from networkx.algorithms.community import louvain_partitions
communities_louvain = []
modularities_louvain = []
louvain = louvain_partitions(socialization_graph, weight="weight") # Bibliografia: [Ref.48] i [Ref.2] --> Ús 6
for elem in louvain:
num_comms = len(elem)
mod = nx.community.modularity(socialization_graph, elem, weight='weight') # Bibliografia: [Ref.45]
communities_louvain.append(num_comms)
modularities_louvain.append(mod)
print(f"Mida communitats mètode de Louvain: {communities_louvain}\n")
print(f"Modularitat de les comunitats de l'algorisme Louvain: {modularities_louvain}")
Mida communitats mètode de Louvain: [18, 7] Modularitat de les comunitats de l'algorisme Louvain: [0.36652907075912095, 0.38806885256571383]
plt.figure(figsize=(20,20))
plt.plot(communities_louvain, modularities_louvain, label="Louvain", color="red")
plt.plot(data_x_socialization, data_y_socialization, label="Girvan-Newman", color="green")
plt.legend()
plt.locator_params(axis='x', nbins=20) # Bibliografia: [Ref.18]
plt.locator_params(axis='y', nbins=20) # Bibliografia: [Ref.18]
plt.ylabel("Modularitat", fontsize=15)
plt.xlabel("Nombre de comunitats", fontsize=15)
plt.grid()
plt.title("Comparativa de l'evolució de la modularitat entre els algorismes LPA i Girvan-Newman", fontsize=20)
plt.show()
Comparativa Louvain - Girvan-Newman
Es pot observar que amb el mètode de Louvain, sempre s'obté una modularitat molt superior que amb el mètode de Girvan-Newman.
Pel que fa al nombre de comunitats, s'observa que l'algorisme de Girvan-Newman mostra una evolució desde 3 (primer nivell) comunitats fins a 22 (últim nivell). L'algorisme de Louvain en el primer pas d'execució té 16 comunitats i en l'últim baixa fins a 6.
Finalment, la complexitat de l'algorisme de Louvain és de θ(n * log(n)) i l'algorisme de Girvan-Newman té una complexitat θ($n^2$ * $m^2$) on m son les arestes del graf i n els nodes.
# Bibliografia: [Ref.49] i [Ref.50]
nx.write_gexf(socialization_graph, "socialization.gexf") # Bibliografia: [Ref.51]
nx.write_gexf(forage_graph, "forage.gexf") # Bibliografia: [Ref.51]
IMPORTANT: Les visualitzacions dels grafs s'han creat amb Gephi Lite. En el moment de l'entrega de la PAC al CV, s'entregarà el document PDF d'aquest apartat.
Referències externes:
[Ref.42] -- girvan_newman [en línia] [consulta:11 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.community.centrality.girvan_newman.html --> Documentació de la funció per aplicar l'algorisme de Girvan-Newman.
[Ref.43] -- Python Iterators [en línia] [consulta:11 de novembre de 2025]. Disponible a: https://www.w3schools.com/python/python_iterators.asp --> Web que explica com funcionen els iteradors en python. [Ref.42] retorna un iterador.
[Ref.44] -- Python max() [en línia] [consulta:11 de novembre de 2025]. Disponible a: https://www.programiz.com/python-programming/methods/built-in/max --> Web que explica la funció max().
[Ref.45] -- modularity [en línia] [consulta:11 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.community.quality.modularity.html --> Documentació de la funció que calcula la modularitat d'una aprtició d'un graf.
[Ref.46] -- Modularity (networks) [en línia] [consulta:11 de novembre de 2025]. Disponible a: https://en.wikipedia.org/wiki/Modularity_(networks)) --> Pàgina de Wikipedia que explica lamodularitat de les xarxes.
[Ref.47] -- Principales Algoritmos de Detección de Comunidades [en línia] [consulta:12 de novembre de 2025]. Disponible a: https://www.grapheverywhere.com/principales-algoritmos-de-deteccion-de-comunidades/ --> Web que explica els principals algorismes de detecció de comunitats.
[Ref.48] -- louvain_partitions [en línia] [consulta:12 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.community.louvain.louvain_partitions.html#networkx.algorithms.community.louvain.louvain_partitions --> Documentació de la funció per aplicar el mètode de Louvain. En aquesta funció es pot veure pas a pas l'historic de comunitats i els nodes que les conformen.
[Ref.49] -- Método de Louvain [en línia] [consulta:12 de novembre de 2025]. Disponible a: https://es.wikipedia.org/wiki/M%C3%A9todo_de_Louvain --> Pàgina de Wikipedia on explica el mètode de Louvain.
[Ref.50] -- Finding the Time Complexity of Girvan-Newman: Part 2 [en línia] [consulta:12 de novembre de 2025]. Disponible a: https://medium.com/smucs/finding-the-time-complexity-of-girvan-newman-part-2-9e5e9f55477d --> Web dedicada a continuar l'explicació del calcul de complexitat de l'algorisme Girvan-Newman.
[Ref.51] -- How to store a networkx graph for visualizing in Gephi? [en línia] [consulta:12 de novembre de 2025]. Disponible a: https://stackoverflow.com/questions/46008727/how-to-store-a-networkx-graph-for-visualizing-in-gephi --> Conversa d'StackOverflow que mostra com guardar els grafs en un fitxer per poder veure'ls i manipular-los en Gephi.
Acabarem l’activitat amb una segona lectura[2]. En aquest cas es tracta d’un article científic que planteja dos mètodes algorítmics de detecció de comunitats basats en el concepte dels Random walks.
[2] Ballal, A., Kion-Crosby, W. B., & Morozov, A. V. (2022). Network community detection and clustering with random walks. Physical Review Research, 4(4), 043117. https://doi.org/10.1103/PhysRevResearch.4.043117
D’una banda, et demanem que facis una lectura detallada del mateix i responguis les següents qüestions:
a) Explica amb les teves paraules en què es basen cadascun dels mètodes de l’article. (0,5 punts)
b) Replica el model WLCF i aplica’l a la xarxa d’interaccions socials dels dofins imprimint el nombre de comunitats obtingudes, la quantitat de nodes en cadascuna d’elles i el valor final de modularitat. Realitza una visualització que permeti una millor comprensió dels resultats. Finalment, explica els blocs del codi i les dificultats que t’hagis anat trobant fins que aquest t’hagi permès obtenir resultats adequats. (1,25 punts)
Apartat a
Mètode "Walk-Likehood Algorithm" WLA
El mètode WLA és basa en utilitzar la inferència bayesiana sobre les propietats d'un graf explorat per random walks per calcular la probabilitat de que cada node del graf pertanyi a una comunitat m (el nombre de comunitats es conegut). El mètode WLA farà, en cada iteració, una partició diferent basant-se en la partició que ha fet en la iteració anterior (en el cas de la primera iteració, l'algorisme utilitza una partició inicial que pot ser aleatòria, extreta d'un prior informatiu o donada per un algorisme, com per exemple, Non-negative Matrix Factorization (NMF)). En el cas d'aquest paper, es considera que WLA ha trobat la divisió òptima dels nodes del graf en comunitats quan la mètrica Normalized Mutual Information (NMI), entre la partició actual i la de la iteració anterior, és menor o igual a 0.99.
Aquest algorisme considera que tant els nodes com els pesos de les arestes del graf són coneguts i realitza cada partició tenint en compte el nombre de cops que un conjunt de random walks arriba a cada node del graf. Cal tenir en compte, la premisa base que un random walk, visitarà més cops els nodes de la pròpia comunitat que els nodes d'una altra comunitat.
Mètode "Walk-Likehood Community Finder" WLCF
El mètode WLCF està pensat per a obtenir el nombre òptim de comunitats del graf (a diferència del WLA, WLCF no sap en quantes comunitats s'ha de particionar el graf).
Aquest mètode comença la seva execució considerant tot el graf com una sola comunitat.
A cada iteració que realitza l'algorisme, el primer que aquest fa es dividir en dos cada comunitat existent en aquella iteració. És a dir, la comunitat $C_{1}$, és divideix en les comunitats $C'_{1}$ i $C'_{2}$. Un cop totes les comunitats del graf han estat dividides en dos, s'executa l'algorisme WLA (s'han dividit les comunitats en dos, per tant, el nombre de comunitats és el doble de la iteració anterior) per obtenir la partició òptima del graf en aquella iteració. Amb la partició òptima del graf de la iteració, es calcula la modularitat i es comproba si combinar algun parell de comunitats augmenta la modularitat. En cas que la modularitat augmenti, es combinen les dues comunitats. Aquests passos s'aniràn executant fins que la mètrica Normalized Mutual Information (NMI) entre la divisió d'aquesta iteració i la de la iteració anterior sigui major a 0.99 o la modularitat decreix més de 0.01 o si s'ha ssolit el nombre màxim d'iteracions.